/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        34.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/9 0:03
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 */
#include "../header.h"

class Solution {
public:
    vector<int> searchRange(vector<int> &nums, int target) {
        vector<int> range(2, -1);
        int left = find_range(nums, target, true);
        if (left == nums.size() || nums[left] != target)
            return range;
        range[0] = left;
        range[1] = find_range(nums, target, false) - 1;
    }

private:
    int find_range(vector<int> &nums, int target, bool left_range) {
        int lo = 0;
        int hi = nums.size();
        while (lo < hi) {
            int mid = ((hi - lo) >> 1) + lo;
            if (nums[mid] > target || (nums[mid] == target && left_range))
                hi = mid;
            else
                lo = mid + 1;
        }
        return lo;
    }
};
